/*
 * Proyecto Final: Computacion Evolutiva
 * Algoritmos GenÃ©ticos en la soluciÃ³n del problema de las N-Reinas
 */
package nqueensga;

import java.util.*;
import javax.swing.JOptionPane;

/**
 *
 * @author Jorge OrdoÃ±ez Mendez 0843419
 *         Gina Natalia CerÃ³n 0744321
 */
public class NQueensGA {
    ArrayList<CromosomaQueens> poblacion;
    int k_individuos, n_queens,tam_queens; // n_individuos: cantidad mÃ¡xima de cromosomas, 
    String solucion= null;                                //k_individuos: cantidad de cromosomas a elegir para el mating pool
    String solucionTablero= null;
    Random generadorAleatorio;
    int contAleatorio;
    private int MAXIMO_USO_SEMILLA;
    public NQueensGA(int n_queens){
        MAXIMO_USO_SEMILLA=(Integer.MAX_VALUE);
        this.n_queens=n_queens;
        this.tam_queens=n_queens;//Ojo antes era n_queens-1 incurrÃ­ en error por lo que lo cambiÃ©, 
                                 //en rand se hace entre 0 y n_queens
//        this.tam_queens=n_queens-1;
        int tam_pob;
        if(n_queens<5){
            tam_pob=18;
        }else{
            double log101622= Math.log((double)n_queens)/Math.log(1.017);
            tam_pob=(int)Math.round(log101622);
        }
        System.out.println("N:"+n_queens+", tamPob: "+tam_pob);
        k_individuos=70;
        generadorAleatorio= new Random(System.currentTimeMillis());
        contAleatorio=0;
        generarPobInicial(tam_pob);
    }
    
    public NQueensGA(int n_queens, int maxUsoSemilla){
        MAXIMO_USO_SEMILLA=maxUsoSemilla;
        this.n_queens=n_queens;
        this.tam_queens=n_queens;//Ojo antes era n_queens-1 incurrÃ­ en error por lo que lo cambiÃ©, 
                                 //en rand se hace entre 0 y n_queens
//        this.tam_queens=n_queens-1;
        int tam_pob;
        if(n_queens<5){
            tam_pob=factorial(n_queens);
        }else{
            double log101622= Math.log((double)n_queens)/Math.log(1.017);
            tam_pob=(int)Math.round(log101622);
        }
        System.out.println("N:"+n_queens+", tamPob: "+tam_pob);
        k_individuos=70;
        generadorAleatorio= new Random(System.currentTimeMillis());
        contAleatorio=0;
        generarPobInicial(tam_pob);
    }
    
    //Funcion: generar la poblacion inicial, instanciando el arreglo config que representa un tablero sencillo que
    //          se usara como base para permutar. Ej: para n=4 config=[1,2,3,4]
    private void generarPobInicial(int tam_pob){
        int []config;
        poblacion=new ArrayList<CromosomaQueens>(tam_pob);
        config= new int[n_queens];
        for(int i=0; i<n_queens;i++)
        {
            config[i]=i;
        }
        
        //Estructura donde garantizo que no hayan repeticiones.
        HashMap<String,ArrayList<CromosomaQueens>> poblacionInicial= new HashMap<String, ArrayList<CromosomaQueens>>(tam_pob);
        //Cromosoma original
        int gen1,gen2;
        CromosomaQueens cromoOriginal= new CromosomaQueens(n_queens, config);
        CromosomaQueens hijoTmp= superMutar(cromoOriginal);
        CromosomaQueens hijoPrevio;
        ArrayList<CromosomaQueens>cromos= new ArrayList<CromosomaQueens>();
        cromos.add(hijoTmp);
        poblacionInicial.put(hijoTmp.toString(),cromos);
        if(hijoTmp.getAptitud()==1.0){ 
	  solucion=hijoTmp.matrizSolucion();
	  solucionTablero=hijoTmp.toString();
	  //solucion=hijoTmp.toString();
	  //solucionArray=Arrays.copyOf(hijoTmp.getTablero(), n_queens);
	}
        poblacion.add(hijoTmp);
        
        //Controlo que no haya repeticiones en la poblaciÃ³n 
        //
        for (int i =1; i< tam_pob; i++){
            hijoPrevio=(CromosomaQueens) hijoTmp.clone();
            //Hago mutaciÃ³n
            //
            do{
                gen1=generarAleatorio(tam_queens);
                gen2=generarAleatorioDif(gen1, tam_queens);
                hijoTmp=hijoPrevio.mutar(gen1,gen2);
            }while(estaEnHashList(poblacionInicial,hijoTmp));
            
            if(poblacionInicial.containsKey(hijoTmp.toString()))
                cromos=poblacionInicial.remove(hijoTmp.toString());
            else
                cromos= new ArrayList<CromosomaQueens>();
            cromos.add(hijoTmp);
            poblacionInicial.put(hijoTmp.toString(),cromos);
//            poblacionInicial.put(hijoTmp.toString(),false);
            //Debug
//            System.out.println("TamaÃ±oPoblaciÃ³n: "+poblacion.size());
//            System.out.println("mutacion["+i+"]:\t"+hijoTmp+", apt:"+hijoTmp.getAptitud());
            poblacion.add(hijoTmp);
        }
//        imprimirHashList(poblacionInicial);
    }
    
    private void imprimirHashList(HashMap<String,ArrayList<CromosomaQueens>> hashList){
        for (Map.Entry<String, ArrayList<CromosomaQueens>> entry : hashList.entrySet()) {
            String string = entry.getKey();
            ArrayList<CromosomaQueens> arrayList = entry.getValue();
            System.out.print("HashList["+string+"]: ");
            System.out.print("{");
            for (Iterator<CromosomaQueens> it = arrayList.iterator(); it.hasNext();) {
                CromosomaQueens cromosomaQueens = it.next();
                System.out.print(cromosomaQueens.toString());
                if(it.hasNext())System.out.print(",");
            }
            System.out.print("}\n");
        }
    }
    
    private boolean estaEnHashList(HashMap<String,ArrayList<CromosomaQueens>>hashList,CromosomaQueens hijoTmp){
        if(hashList.containsKey(hijoTmp.toString())){
            //Debug
//            System.out.println("Esta en hasList: "+hijoTmp);
            ArrayList<CromosomaQueens>listaCromos= hashList.get(hijoTmp.toString());
            boolean esta= listaCromos.contains(hijoTmp);
//            System.out.println("Esta en lista: "+listaCromos.contains(hijoTmp));
            return esta;
        } else
            return false;
        
    }
    
    private int generarAleatorio(int cota){
        int numero= generadorAleatorio.nextInt(cota);
        contAleatorio++;
        alternarSemilla();
        return numero;
    }
    
    private void alternarSemilla()
    {
        if(contAleatorio>MAXIMO_USO_SEMILLA){
            contAleatorio=0;
            generadorAleatorio.setSeed(System.currentTimeMillis());
            System.out.println("AlternÃ© la semilla y puse: "+System.currentTimeMillis());
        }
    }
    
    private int generarAleatorioDif(int valor, int cota){
        int numero=0;
        do{
            numero=generadorAleatorio.nextInt(cota);
            contAleatorio++;
        }while(numero==valor);
        alternarSemilla();
        return numero;
    }
    
    public CromosomaQueens superMutar(CromosomaQueens cromo){
        int contaMutaciones=0;
        int gen1, gen2;
        //Debug
//        System.out.println("SuperMutar:cromo_hijoInicial: "+cromo_hijo);
        int tope= (int)Math.round(Math.log(n_queens)/Math.log(1.06));
        //Debug
//        System.out.print("SuperMutar: tope: "+tope);
        int minTop=(int)Math.round((double)tope*0.25);
        //Debug
//        System.out.print(", minTope: "+minTop);
//        Random rand=new Random(System.currentTimeMillis());
        int mutaciones=0;
        //Deben realizarse por lo menos nQ/2 mutaciones
        do{
            mutaciones=generarAleatorioDif(0, tope);
        }while (mutaciones<= minTop);
        //Debug
//        System.out.print(", n_mutaciones: "+mutaciones);
//        int contaMutaciones=0;
        //Debug
//        System.out.println("n_mutaciones: "+mutaciones+", minTope: "+minTop+", tope: "+tope);
        CromosomaQueens cromo_hiijo=cromo;
        while(mutaciones>contaMutaciones){
            gen1=generarAleatorio(tam_queens);
            gen2=generarAleatorioDif(gen1, tam_queens);
            CromosomaQueens tmp=cromo_hiijo.mutar(gen1,gen2);
            //Debug
//            System.out.println("Mutacion ["+contaMutaciones+"]: "+tmp);
            cromo_hiijo=tmp;
            //Debug
//            System.out.println("Hijo ["+contaMutaciones+"]: "+cromo_hijo);
            contaMutaciones++;
        }
        
        return cromo_hiijo;
    }
    
    private int factorial(int n){
       int resultado=1;

       if (n< 2 && n>=0) resultado=1;
       else
       {
           for (int i=2; i<=n; i++)
           {
               resultado= resultado*i;
           }
       }
       return resultado;
   }
    
    public ArrayList<CromosomaQueens> seleccionar(int nCromosomas){
        ArrayList<CromosomaQueens> matingPool=new ArrayList<CromosomaQueens>(nCromosomas);
        int rand1, rand2;
        CromosomaQueens cromo1, cromo2;
        
        int tamPob=poblacion.size();
        for(int i=0; i<nCromosomas; i++){
            rand1=generarAleatorio(tamPob);
            rand2=generarAleatorioDif(rand1, tamPob);
            
            cromo1 = poblacion.get(rand1);
            cromo2 = poblacion.get(rand2);
            
            if(cromo1.getAptitud()> cromo2.getAptitud()) matingPool.add(cromo1);
            else matingPool.add(cromo2);
        }
        
        return matingPool;
    }
    
    public ArrayList<CromosomaQueens> reproducir(ArrayList<CromosomaQueens> mathinPool, double probMutacion){
        int tamMathPool= mathinPool.size();
        int hijos = (int)Math.round((double)tamMathPool*1.6);
        ArrayList<CromosomaQueens> cromosHijos = new ArrayList<CromosomaQueens>(hijos);
        int cotaInfSeg,cotaSupSeg,codonI,amplitudReg,posFin,nCromoOp;
        double randOp;
        CromosomaQueens cromoOp;
        double probRepro=1-probMutacion;
        for(int i=0; i<mathinPool.size(); i++){
            randOp=generadorAleatorio.nextGaussian();//Hago esto para tener ligera preferencia por la sexual
            
            cromoOp=mathinPool.get(i);
            if(randOp<probRepro){
                nCromoOp=generarAleatorioDif(i,tamMathPool);
                
                cotaInfSeg=(int)Math.round((double)n_queens*0.4);
                cotaSupSeg=(int)Math.round((double)n_queens*0.8);
                //Punto de inicio y amplitud que se conservaran.
                //Verificar que se conserve entre el 80% y el 40% del cromosoma
                codonI=generarAleatorio((int)Math.round((double)n_queens*0.6));
                //Debug:
//                System.out.print("CodonI: "+codonI);
                do{
                    amplitudReg=generarAleatorio(cotaSupSeg);
                    posFin=codonI+amplitudReg;
                }while (cotaInfSeg>amplitudReg || posFin>=n_queens);
                
                cromosHijos.addAll(cromoOp.reproducirCon(mathinPool.get(nCromoOp),codonI,posFin));
            }
            else{
                int gen1= generarAleatorio(tam_queens);
                int gen2= generarAleatorioDif(gen1, tam_queens);
                
                cromosHijos.add(cromoOp.mutar(gen1, gen2));
            }
        }
        
        return cromosHijos;
    }
    
    public void reemplazar(ArrayList<CromosomaQueens> hijos, int edadMuerte
            , double tazaMortandad, double prefMuertPeor){
        CromosomaQueens cromoTmp;
        int cromoRand;
        int tamPob=poblacion.size();//cantidad de cromosomas en la poblaciÃ³n;
        cromoRand=generarAleatorio(tamPob);
        double razonMuertes;
        
        //Controlo la poblaciÃ³n con edades
        //
        for(int i=0; i<poblacion.size(); i++){
            cromoTmp= poblacion.remove(i);
            cromoTmp.incrementarEdad();
            if(!(cromoTmp.getEdad()>edadMuerte))poblacion.add(cromoTmp);
        }
        //AÃ±ado hijos a la poblaciÃ³n, lo hice asÃ­ para vaciar la lista de hijos
        //
//        System.out.print("Numero Hijos: "+hijos.size());
        do{
            cromoTmp=hijos.remove(0);
            if(cromoTmp.getAptitud()==1.0){
                solucion=cromoTmp.matrizSolucion();
                solucionTablero=cromoTmp.toString();
		return;
            }
            
            poblacion.add(cromoTmp);
        }while(!hijos.isEmpty());
        //Genero mortandad que a lo sumo puede ser el mayor valor de taaza de mortandad
        double minRazMuertes=0.25;
        do{
            razonMuertes= generadorAleatorio.nextGaussian();
        }while(razonMuertes>tazaMortandad || razonMuertes<minRazMuertes);
        if(poblacion.size()>10000) razonMuertes=tazaMortandad;
        int numCromosAMatar=(int)Math.round(razonMuertes*(double)poblacion.size());
        //Mato aleatoriamente cromosomas con torneo aleatorio prefiriendo los de peor aptitud
        //
        double preferenciaAptitud;//Variable para que la aleatoriedad prefiera matar peores
        int rand1,rand2;
        
//        System.out.print(", Muertes en este reemplazo: "+numCromosAMatar);
        
        for(int i=0;i<numCromosAMatar;i++){
            tamPob=poblacion.size();
            preferenciaAptitud=generadorAleatorio.nextGaussian();//Valor entre cero y uno para evento de
            //muerte del peor
            rand1=generarAleatorio(tamPob);
            rand2=generarAleatorioDif(rand1, tamPob);
            CromosomaQueens cromo1,cromo2;
            cromo1=poblacion.get(rand1);
            cromo2=poblacion.get(rand2);
            //Controlo preferencia a los peores, pero tambien pueen morir mejores
            if(preferenciaAptitud<prefMuertPeor){
                if(cromo1.getAptitud()>cromo2.getAptitud())
                    poblacion.remove(rand2);
                else poblacion.remove(rand1);
            }else{
                if(cromo1.getAptitud()>cromo2.getAptitud())
                    poblacion.remove(rand1);
                else poblacion.remove(rand2);
            }
        }
//        System.out.println(", TamaÃ±o de polbaciÃ³n: "+poblacion.size());
        
    }
    
    public int getNumMatPool(){
        return (int)Math.round((double)poblacion.size()*0.75);
    }
    
    
    public void imprimirPoblacion(ArrayList<CromosomaQueens> poblacion ,double filtroApt){
        int i=0;
        for (Iterator<CromosomaQueens> it = poblacion.iterator(); it.hasNext();) {
            CromosomaQueens object = it.next();
            if(filtroApt<=object.getAptitud()){
                System.out.println("Cromsoma["+i+"]: "+object.toString()+", apt:"+object.getAptitud());
                i++;
           }   
        }
    }
    
    
    public ArrayList<CromosomaQueens> muestrearPoblaci(int muestras){
        HashMap<String, Boolean> muestra = new HashMap<String, Boolean>();
        int idmuestra=0;
        CromosomaQueens muestrica=null;
        ComparadorCromosomas comp = new ComparadorCromosomas();
        PriorityQueue<CromosomaQueens> colaPriorCromos = new PriorityQueue<CromosomaQueens>(muestras,comp);
        
        for(int i=0;i<muestras;i++){
            
            do{
                idmuestra=generarAleatorio(poblacion.size());
                muestrica=poblacion.get(idmuestra);
            }while(muestra.containsKey(muestrica.toString()));
            muestra.put(muestrica.toString(), true);
            colaPriorCromos.add(muestrica);
        }
        ArrayList<CromosomaQueens> cromos= new ArrayList<CromosomaQueens>(muestras);
        while (!colaPriorCromos.isEmpty()) {
            CromosomaQueens object = colaPriorCromos.remove();
            cromos.add(object);
        }
        return cromos;
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int n;
	do{
	  n=Integer.parseInt(JOptionPane.showInputDialog("Ingrese la cantidad de reinas valores [3-...]: "));
        }while(n<=3);
        //A nqueens le digo cada cuanto voy a actualizar la semilla
	int cotaIter, contIter, edadCromo;
	cotaIter=0; contIter=0;
	double tazaMaxMortandad, preferenciPeores;
	do{
	  cotaIter=Integer.parseInt(JOptionPane.showInputDialog("A cuantas generaciones desea acotar valores [1-...]?: "));
        }while(cotaIter<=0);
	do{
	  edadCromo=Integer.parseInt(JOptionPane.showInputDialog("Cual sera edad de muerte general cromsomas Valores [1-...]: "));
        }while(edadCromo<=0);
	do{
	  tazaMaxMortandad=Double.parseDouble(JOptionPane.showInputDialog("MortandadMaxima de poblacion valores [0.0-1.0]"));
        }while(tazaMaxMortandad<0 && tazaMaxMortandad>1);
	do{
	  preferenciPeores=Double.parseDouble(JOptionPane.showInputDialog("Preferencia remplazo peores valores [0.0-1.0]"));
        }while(preferenciPeores<0 && preferenciPeores>1);
        double probMuta;
	do{
	  probMuta=Double.parseDouble(JOptionPane.showInputDialog("Prob. de mutación en Matting pool valores [0.0-1.0]: "));
        }while(probMuta<0 && probMuta>1);
        //Instancio
        //
        NQueensGA objNqueens= new NQueensGA(n);
        ArrayList cromosomasTmp;
        ArrayList<CromosomaQueens> muestra=null;
        String solucion= null;
        while(objNqueens.solucion==null && contIter<cotaIter){
            cromosomasTmp= objNqueens.seleccionar(objNqueens.getNumMatPool());
            cromosomasTmp=objNqueens.reproducir(cromosomasTmp, probMuta);
            //CromosomasHijos,edadMuerte,tazaMortandadmaxima,PreferenciaporMatarPeores
            objNqueens.reemplazar(cromosomasTmp,edadCromo,tazaMaxMortandad,preferenciPeores);
	    contIter++;
            //DEBUG
            //muestra= objNqueens.muestrearPoblaci(10);
            //System.out.println("ObtuveMuestra IteraciÃ³n =============>:"+contIter);
            //objNqueens.imprimirPoblacion(muestra,0.5);
            //System.out.println("Tam. Poblacion: "+objNqueens.poblacion.size());
        }
        if(objNqueens.solucion!=null)JOptionPane.showMessageDialog(null,"Solución ENCONTRADA: "+objNqueens.solucionTablero+":\n"+objNqueens.solucion);
        else JOptionPane.showMessageDialog(null,"No se encontró solucion");        
        //        Random generAleatoMain= new Random(System.currentTimeMillis());
        // TODO: Poner cÃ³digo para prueba sin GUI
        /*CromosomaQueens cromoPrueba;
        int []tabTmp=new int[8];
        
        tabTmp[0]=5;
        tabTmp[1]=7;
        tabTmp[2]=1;
        tabTmp[3]=3;
        tabTmp[4]=4;
        tabTmp[5]=2;
        tabTmp[6]=6;
        tabTmp[7]=0;
        
        cromoPrueba = new CromosomaQueens(8, tabTmp);
                
        System.out.println("cromosoma original");
        for(int i=0;i<8;i++)
        {
            System.out.println(tabTmp[i]+", ");
        }
        
        cromoPrueba=cromoPrueba.mutar(gen1, gen2);
        tabTmp=cromoPrueba.getTablero();
        
        System.out.println("cromosoma mutado");
        for(int i=0;i<8;i++)
        {
            System.out.println(tabTmp[i]+", ");
        }
        */
        
        ///////
        //Còdigo de prueba JORGE para reproducciòn por cruce ordenado
        ///////
//        System.out.println("==============PRUEBA PARA REPRODUCCIÓN==============");
//        int [] arrayM= {0,1,2,3,4,5,6,7};
//        int [] arrayP= {6,5,2,7,3,1,0,4};
//        CromosomaQueens cromoMama= new CromosomaQueens(8, arrayM);
//        CromosomaQueens cromoPapa= new CromosomaQueens(8, arrayP);
//        cromoMama.calcularAptitud();
//        cromoPapa.calcularAptitud();
//        
//        System.out.print("Mama: [");
//        for(int i=0; i<8; i++){
//            System.out.print(arrayM[i]+", ");
//        }
//        System.out.println("]");
//        
//        System.out.print("Papa: [");
//        for(int i=0; i<8; i++){
//            System.out.print(arrayP[i]+", ");
//        }
//        System.out.println("]");
//        //DEbug
////        System.out.println("Termino los calculos de aptitud");
//        int codonI, cotaInfSeg, cotaSupSeg,posFin, amplitudReg;
//        cotaInfSeg=(int)Math.round((double)8*0.4);
//                cotaSupSeg=(int)Math.round((double)8*0.8);
//                //Punto de inicio y amplitud que se conservaran.
//                //Verificar que se conserve entre el 80% y el 40% del cromosoma
//                codonI=generAleatoMain.nextInt((int)Math.round((double)8*0.6));
//                //Debug:
////                System.out.print("CodonI: "+codonI);
//                do{
//                    amplitudReg=generAleatoMain.nextInt(cotaSupSeg);
//                    posFin=codonI+amplitudReg;
//                }while (cotaInfSeg>amplitudReg || posFin>=8);
//        ArrayList<CromosomaQueens> cromoHijos = cromoMama.reproducirCon(cromoPapa, codonI, posFin);
//        //Debug
////        System.out.println("Termino reproducción");
//        int j=0;
//        
//        while(!cromoHijos.isEmpty())
//        {
//            j++;
//            int [] arrayTmp=cromoHijos.remove(0).getTablero();
//            System.out.print("Hijo"+j+" sin incognitas: [ ");
//            for(int i=0; i<8; i++){
//                System.out.print(arrayTmp[i]+", ");
//            }
//            System.out.print("]\n");
//        }
    }
}